package org.example.Problem;

import org.junit.Test;
public class MyPriorityQueue {
    private int[] stack;
    private int size = 0;
    public MyPriorityQueue(int len){
        stack = new int[len];
    }
    private int leftSon(int pos){
        return pos*2;
    }
    private int rightSon(int pos){
        return pos*2+1;
    }
    public void add(int x){
        ++size;
        stack[size] = x;
        pushUp(size,x);
    }
    public int peek(){
        if(size<1) return -1;
        return stack[1];
    }
    public int poll(){
        if(size<1) return -1;
        try {
            return stack[1];
        }finally {
            stack[1] = stack[size];
            --size;
            pushDown(1,stack[1]);
        }
    }
    void pushDown(int pos,int val){
        if(leftSon(pos)>size){
            stack[pos] = val;
        }else if(leftSon(pos) == size){
            if(stack[leftSon(pos)]<stack[pos]) {
                stack[pos] = stack[leftSon(pos)];
                pushDown(leftSon(pos),val);
            }
        }else {
            if (stack[leftSon(pos)] >= stack[pos] && stack[rightSon(pos)] >= stack[pos]) stack[pos] = val;
            else if (stack[leftSon(pos)] > stack[pos] && stack[rightSon(pos)] < stack[pos]) {
                stack[pos] = stack[rightSon(pos)];
                pushDown(rightSon(pos), val);
            } else if (stack[leftSon(pos)] < stack[pos] && stack[rightSon(pos)] >= stack[pos]) {
                stack[pos] = stack[leftSon(pos)];
                pushDown(leftSon(pos), val);
            } else {
                if (stack[leftSon(pos)] > stack[rightSon(pos)]) {
                    stack[pos] = stack[rightSon(pos)];
                    pushDown(rightSon(pos), val);
                } else {
                    stack[pos] = stack[leftSon(pos)];
                    pushDown(leftSon(pos), val);
                }
            }
        }
    }
    void pushUp(int pos,int val){
        if(pos == 1) stack[pos] = val;
        else{
            if(stack[pos/2] > stack[pos]) {
                stack[pos] = stack[pos/2];
                pushUp(pos/2,val);
            }else{
                stack[pos] = val;
            }
        }
    }
    public int size(){
        return size;
    }
    public void print(){
        for(int i=1;i<=size;i++){
            System.out.printf("%d ",stack[i]);
        }
        System.out.println();
    }
}
